# 斐波那契数列又称兔子数列，是指这样一个数列：1、1、2、3、5、8、13、21、34、55、89...
# 【每一个数都是它前两个数的和，从1开始】
# 编写程序，找出第n项是什么数


# 方法一：递归
def main_1(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return main_1(n - 1) + main_1(n - 2)


# 方法二：循环
def main_2(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        a = 1
        b = 1
        for i in range(2, n):
            c = a + b
            a = b
            b = c
        return c


if __name__ == "__main__":
    n = 9
    print("斐波那契数列第{}项是：{}".format(n, main_2(n)))
